package week_11;
@SuppressWarnings("all")
public class ShellSort {

    public static void sort(Comparable[] a) {
//    1.根据数组a的长度确定增长量h的增长初试值
        int h = 1;
        while (h < a.length / 2) {
            h = 2 * h + 1;
        }
//    2.希尔排序
        while (h >= 1) {
//          排序
//        2.1 找到待插入的值
            for (int i = h; i < a.length; i++) {
//        2.2 把待插入的元素插入到有序序列中
                for (int j = i; j >= h; j -= h) {
//                    待插入元素是a[j],比如a[j]和a[j-h]
                    if (greater(a[j - h], a[j])) {
//                        交换元素
                        exch(a, j - h, j);
                    } else {
//                        待插入元素已经找到了合适的位置，结束循环
                        break;
                    }
                }
            }
//          2.减少h的值
            h = h / 2;
        }
    }

    private static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
